Batch 3 - Class 231 - Information and Encryption

• (AOPS) Count number of trailing zeros in 320! 
• Answer: 78 (The key insight is that every 5 as a factor yields a trailing zero in the factorial product (when added to an even number, of which there are enough available in the factorial product). Thus there are 320/5=64 multiples of 5. The multiples of 25 give two zeros, and hence need to be added - there are 320/25=12 of these. The multiples of 125 give 3 zeros, and hence need to add those - there are two of those. Total 64+12+2=78)

• Review of previous class
• How to convey information - verbal, symbols, etc
• All information communication involves some coding - binary, ascii etc
• Compression involves finding the smallest length coding - eg: huffman coding
• Based on frequency of different characters. For example, frequency of letters in english language

• Telephone numbers, and STD and ISD codes - what are the assumptions in this design with respect to frequency of calling? How does the system know whether we are dialing local or STD? (notion of non-repeating prefix again)
• Error Detection: Go back to ascii codes, and ask kids how they would design a system so that if there was one bit error in a character, they could detect it. Show that in standard ascii, one bit error may lead to wrong interpretation - A and E differ by one bit, so BAT could become BET.
• Hint: Introduce notion of repetition or redundancy to detect errors.
• Parity bit
• However, with parity, one can't correct the error - Error Correction
• Illustrate one bit being transmitted
• Without any parity bit, one can't detect an error
• If we add a parity bit, we can detect one error (illustrate on a square bit-chart, and where the bits move in case of an error)
• What do we need to correct an error? Can kids figure out how many bits are required? (illustrate with a 3-D bit-cube, and where respective bits go - note that the correction bits themselves can be in error)
• 4 bits need 3 parity bits to correct one error. Let kids learn about it at home if they would like to

• Post the problem of secret communication to kids and let them work in pairs to solve it. Note that to be able to communicate secretly, and not let a person-in-the-middle break in, they need to have something (key) in advance which is a secret
• Most groups came up with some form of substitution cipher
• Puzzle:  Justin Case and Auntie Bellum are fellow con artists who deliver coded messages to each other to communicate. Recently Auntie Bellum was put in jail for stealing a rare and expensive diamond. Only a few days after this, Justin Case sent her a friendly letter asking her how she was. On the inside of the envelope of the letter, he hid a code. Yesterday, Auntie Bellum escaped and left the envelope and the letter inside the jail cell. The police did some research and found the code on the inside of the envelope, but they haven't been able to crack it. Could you help the police find out what the message is?

  This is the code: llwatchawtfeclocklnisksundialcirbetimersool
• Hint: It was a TIMED exit
• Answer: "Loose Bricks In Left Wall"
• Shift/ Caeser Cipher
• You shift each letter by a fixed amount
• Give kids an exercise of what a sentence may look like if we shift by 4
• Note that the information of "shift by 4" is still required to be transmitted

• What are the issues with such a code?
• Can be cracked by looking at frequency distribution (https://www.khanacademy.org/computing/computer-science/cryptography/crypt/pi/frequency-fingerprint-exploration)
• What happens to frequency distribution when you perform shift cipher?
• How can you solve for this issue?
• Substitution Cipher
• You replace each letter by some other letter
• You still need to transmit the code information
• What happens to frequency distribution when you perform substitution cipher?
• You could avoid the issues in above ciphers by making all letters roughly equal frequency
• Polyalphabetic Cipher - you choose a sequence and repeat that. Now code basis that sequence, so that shift of each letter can change.
• Explore  https://www.khanacademy.org/computing/computer-science/cryptography/crypt/pi/polyalphabetic-exploration
• How would you break this kind of cipher?
• Try for different code lengths and look at frequency distribution. For example, guess that code length is 5, hence take every 5th letter in cipher text and look at frequency distribution
• Once the frequency distribution looks like english language, crack it like a regular caeser cipher

• Research - Enigma encryption device and The Bomb, which broke the enigma codes
• Build a shift cipher device at home